//
// Created by francklinson on 2021/7/10.
//
#include <string>
#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;

class TimeMap {
private:
    unordered_map<string, vector<pair<int, string>>> recorder;
public:
    /** Initialize your data structure here. */
    TimeMap() {
    }

    /**
     * 设置键 时间戳 值
     * @param key
     * @param value
     * @param timestamp
     */
    void set(const string &key, const string &value, int timestamp) {
        recorder[key].push_back(make_pair(timestamp, value));
    }

    /**
     * 找到该键对应的 该时间戳的前一个值
     * @param key
     * @param timestamp
     * @return
     */
    string get(const string &key, int timestamp) {
        auto &pairs = recorder[key];
        // 二分找到第一个小等于timestamp的时间戳 返回对应的值
        // 使用一个大于所有 value 的字符串，以确保在 pairs 中含有 timestamp 的情况下也返回大于 timestamp 的位置
        pair<int, string> p{timestamp, string({127})};
        auto i = upper_bound(pairs.begin(), pairs.end(), p); // 第一个大于timestamp的时间戳
        if (i != pairs.begin()) {
            return (i - 1)->second;
        }
        return "";
    }
};

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap* obj = new TimeMap();
 * obj->set(key,value,timestamp);
 * string param_2 = obj->get(key,timestamp);
 */
int main() {
    auto obj = new TimeMap();
    obj->set("foo", "bar", 1);
    cout << obj->get("foo", 3) << endl;
    delete obj;
//    cout << string ({97}) <<endl;  //对应于ascii码
    return 0;
}